package solution;

/**
 * <a href="https://www.nowcoder.com/practice/87c0e7abcbda41e7963660fa7d020995?tpId=117&&tqId=37744&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking">
 * NC48 在旋转过的有序数组中寻找目标值</a>
 *
 * @author or2
 * @Description 给定一个整数数组nums，按升序排序，数组中的元素各不相同。
 * nums数组在传递给search函数之前，会在预先未知的某个下标 t（0 <= t <= nums.length-1）上进行旋转，让数组变为[nums[t], nums[t+1], ..., nums[nums.length-1], nums[0], nums[1], ..., nums[t-1]]。
 * 比如，数组[0,2,4,6,8,10]在下标3处旋转之后变为[6,8,10,0,2,4]
 * 现在给定一个旋转后的数组nums和一个整数target，请你查找这个数组是不是存在这个target，如果存在，那么返回它的下标，如果不存在，返回-1
 * @create 2021年09月02日 时间: 15:50
 */
public class Search48 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param nums   int整型一维数组
     * @param target int整型
     * @return int整型
     */
    public int search(int[] nums, int target) {
//        变量初始化
        int lIndex = 0;
        int rIndex = nums.length - 1;
        int mid = rIndex >> 1;
//        在 [lIndex, rIndex] 区间内进行搜索
        while (lIndex <= rIndex) {
//        找到该元素, 返回其下标
            if (nums[mid] == target) {
                return mid;
            }
//            左边正常情形, 右边可能中间有反转
            if (nums[mid] > nums[lIndex]) {
//                大于该值的数只有可能在右边
                if (target > nums[mid]) {
                    lIndex = mid + 1;
//                正常二分(左边正常情形)
                } else {
                    rIndex = mid - 1;
                }
//            左边可能中间有反转, 右边正常情形
            } else {
//                正常二分
                if (target > nums[mid] && target <= nums[rIndex]) {
                    lIndex = mid + 1;
//                小于该值肯定在左边, 大于该值且比右边边界大也在左边
                } else {
                    rIndex = mid - 1;
                }
            }
            mid = lIndex + (rIndex - lIndex >> 1);
        }
        return -1;
    }
}
